struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
  if (root == nullptr) {
    return nullptr;
  }
  if (root == p || root == q) {
    return root;
  }
  // 左子树
  TreeNode *l = lowestCommonAncestor(root->left, p, q);
  // 右子树
  TreeNode *r = lowestCommonAncestor(root->right, p, q);
  bool t = false;
  if (root == p || root == q) {
    t = true;
  }
  if ((l != nullptr && r != nullptr) || (l != nullptr && t) ||
      (r != nullptr && t)) {
    return root;
  }
  if (l != nullptr) {
    return l;
  }
  if (r != nullptr) {
    return r;
  }
  if (t) {
    return root;
  }
  return nullptr;
}